The present invention relates to a Viterbi decoder, and more particularly to the memory reduction techniques for a Viterbi decoder of Trellis-coded modulation.
Trellis-coded modulation/demodulation has been widely used in many communication systems to improve system performance. It has been shown that the trellis-coded modulation scheme using two-dimensional (2-D) constellations can improve the error performance of synchronous data links without sacrificing data rate or requiring more bandwidth.
Trellis-coded modulation schemes using 4-D constellations have also been reported in recent years. In a paper titled xe2x80x9cTrellis-Coded Modulation with Multidimensional Constellationsxe2x80x9d published in IEEE Transactions on Information Theory, Vol. IT-33, No. 4, July 1987, a number of modulation schemes have been presented and evaluated by Lee-Fan Wei. How to select multi-dimensional constellations, partition them into subsets and construct trellis codes using these subsets as well as how to map bits to constellation points have been discussed in the paper.
Wei""s 16-state 4 dimensional (4-D) trellis code has been adopted by ADSL standards such as TIE1.4 and G.DMT as an option. FIG. 1 shows a trellis diagram of 16-state codes with 4-D constellation. There are 16 states and four branches enter each state. As a result, a total of 64 transitions exist.
A Viterbi decoder may be used as a decoder of Wei""s 16 state 4-D trellis-code. The basic operation of the Viterbi decoder is to select the most likely symbol from the 4-D cosets in Wei""s construction based on a long sequence of received data. Whenever a newly received data is available, several candidates (surviving paths or survivors) are extended and compared with the received data sequence., and the data associated with the best survivor is chosen as the most likely one.
FIG. 2 illustrates the block diagram of a typical Viterbi decoder using a trace-back method. As shown in the block diagram, for each received 4-D signal a branch metric unit 101 computes the branch metrics associated with the 64 transitions. The branch metric associated with each transition is measured in terms of Euclidean distance between the received signal and a symbol in the 4-D cosets that is closet to the received signal. An add-and-compare selector (ACS) 102 determines the survival path for each of the 16 states. A memory unit 103 stores the 4-D symbols as well as the trace-back information for all branches in all the surviving paths that reach the 16 states. A trace-back unit 104 is used to implement the trace-back operation.
As can be seen from FIG. 2, significant memories are required in the decoding process to store the trace-back information as well as the 4-D symbols associated with all the state transitions in each survival path. Assuming a track-back length of 20, the size of the required memory that saves the survival 4-D symbols of each state is 16xc3x9720xc3x978xc3x974 bits. In the conventional implementation, redundant information is stored if the 4-D symbols associated with all state transitions that are selected from the cosets are stored in their original format.
The most commonly used implementation for the trace-back unit 104 is a ROM device which saves the trace-back information as shown in FIG. 3 for a 16-state Wei""s code. As can be seen from FIG. 3, a ROM of size 16xc3x9716xc3x972 bits is required because 2 bits are needed to represent the trace-back information {0, 1, 2, 3} that denotes four possible survivors leading to a specific state.
From the forgoing discussion, it is understandable that there is strong need in improving the conventional implementation of a Viterbi decoder of trellis-coded modulation so as to provide more efficient as well as lower cost decoders.
The present invention has been made to improve the above-mentioned drawbacks of a conventional Viterbi decoder of trellis-coded modulation. The primary object of the invention is to provide mechanisms for reducing memory requirement in the conventional Viterbi decoder. Accordingly, the invention proposes a simple combinational logic circuit to replace the implementation using ROM and an information storage mechanism that helps to reduce the required memory used for storing all the 4-D symbols associated with each state transitions in all survivors for trace-back procedure.
It is also an object of the invention to provide a combinational logic circuit for processing trace-back operation of a Vierbi decoder instead of using a ROM. According to the present invention, the combinational circuit comprises a four-input and one-output multiplexer, a shifter and an adder. The multiplexer provides a trace-back value according to the trace-back information of a state and the shifter shifts the state value towards right by two bits. The trace-back value and shifted value are added together to get the state value of the prior state.
Another object of the invention is to provide a mechanism for reducing the size of the memory storing 4-D symbols of the trace-back information. A 4-D coset is rewritten as a union of two Cartesian product of two 2-D cosets. All the symbols in the eight 4-D cosets closest to a received signal can be represented by symbols from two 2-D cosets along with differences between their coordinates.